'''
    遍历树分三种：前序，中序和后序

    前序遍历：(preorder)
        1.根节点
        2.左子树
        3.右子树
    后序遍历：(postorder)
        1.左节点
        2.右节点
        3.根节点
    中序遍历：()
        1.左节点
        2.根节点
        3.右节点

    然后可以发现，这些方法都可以写进类里面。后序遍历顺序和计算表达式结果顺序是相同的。中序遍历和获取算数表达式的顺序是相同的，下面搞一搞。
'''
import operator

def preOrder(tree):
    if tree:
        print(tree.getRootVal)
        preOrder(tree.getLeftChild())
        preOrder(tree.getRightChild())


def postOrder(tree):
    if tree != None:
        postOrder(tree.getLeftChild())
        postOrder(tree.getRightChild())
        print(tree.getRootVal)

def inorder(tree):
    if tree != None:
        inorder(tree.getLeftChild())
        print(tree.getRootVal)
        inorder(tree.getRightChild())

'''
    现在我们有表达式变成树，树变成表达式，树计算表达式值
'''
# 后序遍历计算表达式
def postordereval(tree):    # 后序遍历计算表达式
    opers = {'+':operator.add,'-':operator.sub,'*':operator.mul,'/':operator.truediv}

    res1 = None
    res2 = None

    if tree:
        res1 = postordereval(tree.getLeftChild())
        res2 = postordereval(tree.getRightChild())

        if res2 and res1:
            return opers[tree.getRootVal()](res1,res2)
        else:
            return tree.getRootVal()

def printexp(tree):
    sval = ''
    if tree:
        sval = '(' + printexp(tree.getLeftChild())
        sval = sval + str(tree.getRootVal())
        sval = sval + printexp(tree.getRightChild()) + ')'

    return sval